package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/'>K 次取反后最大化的数组和(Maximize Sum Of Array After K Negations)</a>
 * <p>给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：</p>
 * <ul>选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。</ul>
 * <p>重复这个过程恰好 k 次。可以多次选择同一个下标 i 。</p>
 * <p>以这种方式修改数组后，返回数组 可能的最大和 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：nums = [4,2,3], k = 1
 *      输出：5
 *      解释：选择下标 1 ，nums 变为 [4,-2,3] 。
 *
 * 示例 2：
 *      输入：nums = [3,-1,0,2], k = 3
 *      输出：6
 *      解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。
 *
 * 示例 3：
 *      输入：nums = [2,-3,-1,5,-4], k = 2
 *      输出：13
 *      解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= nums.length <= 10^4</li>
 *     <li>-100 <= nums[i] <= 100</li>
 *     <li>1 <= k <= 10^4</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/18 14:04
 */
public class LC1005MaximizeSumOfArrayAfterKNegations_S {
    static class Solution {
        public int largestSumAfterKNegations(int[] nums, int k) {
            // 因为数字范围为 -100 <= nums[i] <= 100。
            // 可以使用长度为201的数组统计每个数字出现的次数，从小到大进行取反即可
            // 统计
            int range = 100;
            int[] cnt = new int[2 * range + 1];   // 100 * 2 + 1
            for (int num : nums) {
                cnt[num + range]++;
            }
            // 求和
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            for (int currIdx = 0; k > 0; k--) {
                while (cnt[currIdx] == 0) {
                    ++currIdx;
                }
                if (currIdx - range >= 0) {
                    if ((k & 1) == 1) {
                        sum -= 2 * (currIdx - range);
                    }
                    break;
                }
                cnt[currIdx]--;
                //cnt[-(currIdx - range) + range]++;
                cnt[2 * range - currIdx]++;
                //sum += 2 * (-(currIdx - range));
                sum += 2 * (range - currIdx);
            }
            return sum;

            // 从小到大排序
            // 对于小于0的数，从小到达取反。会出现两种情况：
            //      1.所有的负数被取反，此时所有数>=0，只需要选择最小的数反复取反即可
            //      2.部分的负数被取反，此时k==0，因为数组从小到大排序，较小的先被取反
            //Arrays.sort(nums);
            //for (int currIdx = 0; currIdx < nums.length && nums[currIdx] < 0 && k > 0; ++currIdx, --k) {
            //    nums[currIdx] = -nums[currIdx];
            //}
            //if ((k & 1) == 1) {
            //    Arrays.sort(nums);
            //    nums[0] = -nums[0];
            //}
            //int sum = 0;
            //for (int num : nums) {
            //    sum += num;
            //}
            //return sum;

            // 小根堆
            //PriorityQueue<Integer> queue = new PriorityQueue<>(nums.length);
            //for (int num : nums) {
            //    queue.add(num);
            //}
            //for (int i = 0; i < k; i++) {
            //    queue.add(-queue.poll());
            //}
            //int sum = 0;
            //while (!queue.isEmpty()) {
            //    sum += queue.poll();
            //}
            //return sum;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.largestSumAfterKNegations(new int[]{4, 2, 3}, 1));                  //  5
        System.out.println(solution.largestSumAfterKNegations(new int[]{3, -1, 0, 2}, 3));              //  6
        System.out.println(solution.largestSumAfterKNegations(new int[]{2, -3, -1, 5, -4}, 2));         //  13
        System.out.println(solution.largestSumAfterKNegations(new int[]{-8, 3, -5, -3, -5, -2}, 6));    //  22
    }
}
